import java.util.*;

/**
 * 1769. 移动所有球到每个盒子所需的最小操作数
 * https://leetcode-cn.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/
 */
public class Solutions_1769 {
    public static void main(String[] args) {
        String boxes1 = "110";  // output: {1, 1, 3}
        String boxes2 = "001011";  // output: {11, 8, 5, 4, 3, 4}

        List<String> inputs = new ArrayList<>();
        inputs.add(boxes1);
        inputs.add(boxes2);

        for (String input : inputs) {
            int[] result = minOperations(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 解法二：贪心法（3ms）
     * 解题思路：
     * 1. 记录下每个元素，左右两侧字符 '1' 的个数
     * 2. 循环计算出第 1 个字符（索引 0）需要的操作数
     * 3. 后面的操作数可由前一个操作数计算得到
     *      例如：001011
     *      res[0] = 11
     *      res[1] = res[0] - 右侧 1 的个数 + 左侧 1 的个数
     *      res[2] = res[1] - 右侧 1 的个数 + 左侧 1 的个数 - 1
     *      res[3] = res[2] - 右侧 1 的个数 + 左侧 1 的个数
     *      如果本身是字符 1，还需要减 1
     * 关键：索引每后移 1 位，就与右侧的每一个 1 更进了一步，可以少操作 1 次
     *      与左侧的每一个 1 更远了一步，需要多操作 1 次
     */
    public static int[] minOperations(String boxes) {
        char[] arr = boxes.toCharArray();
        int len = arr.length;
        // leftCnt[5] = 2：boxes 中，索引 5 的左侧有 2 个字符 '1'
        int[] leftCnt = new int[len];
        // rightCnt[5] = 2：boxes 中，索引 5 的右侧有 2 个字符 '1'
        int[] rightCnt = new int[len];

        int cnt = 0;
        for (int i = 0; i < len; i++) {
            leftCnt[i] = cnt;
            if (arr[i] == '1') {
                cnt ++;
            }
        }
        cnt = 0;
        for (int i = len - 1; i >= 0; i--) {
            rightCnt[i] = cnt;
            if (arr[i] == '1') {
                cnt ++;
            }
        }

        int[] res = new int[len];
        // 计算出 res[0] 需要的操作数
        for (int i = 1; i < len; i++) {
            if (arr[i] == '1') {
                res[0] += i;
            }
        }
        // 根据 res[0] 依次推导出后续索引需要的操作数
        for (int i = 1; i < len; i++) {
            res[i] = res[i - 1];
            // 右侧 n 个球，即减少 n 步操作
            res[i] -= rightCnt[i];
            // 左侧 n 个球，即增加 n 步操作
            res[i] += leftCnt[i];
            if (arr[i] == '1') {
                // 关键：本身是字符 '1' 时，减 1
                res[i] -= 1;
            }
        }
        return res;
    }

    /**
     * 解法一：暴力法（238ms）
     * 解题思路：
     * 1.将 boxes 中每个字符 '1' 的索引，加入到 list 中
     * 2.遍历 boxes，将每个元素与 list 中的元素进行减法操作
     */
    public static int[] minOperations2(String boxes) {
        List<Integer> list = new ArrayList<>();
        int[] res = new int[boxes.length()];
        for (int i = 0; i < boxes.length(); i++) {
            if (boxes.charAt(i) == '1') {
                list.add(i);
            }
        }
        for (int i = 0; i < boxes.length(); i++) {
            for (int idx : list) {
                res[i] += Math.abs(i - idx);
            }
        }
        return res;
    }
}
